Exercici 6 (Tasca 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages))
Classificació VI: variacions de K
Per a cada un dels següents llenguatges L, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R}, o L \notin \mathbf{RE} \cup \mathbf{coRE}.
- L = K \times K
- L = \overline{K} \times K
- L = \overline{K} \times \overline{K}
- L = \overline{\overline{K} \times K}
Nota
Recordeu que
K = \{ n \mid M_n(n)\!\downarrow \}\ ,
on M_n és la màquina de Turing amb nombre de Gödel n i \downarrow indica que s’atura.